#include <iostream>
#include <vector>
using namespace std;

// 计算最小邮票张数
int minStamps(const vector<int>& stamps, int amount) {
    // 初始化动态规划数组
    vector<int> dp(amount + 1, -1);
    dp[0] = 0; // 金额为0时，不需要任何邮票

    // 动态规划填表
    for (int i = 0; i < amount; ++i) {
        if (dp[i] >= 0) { // 细节1：dp[i] == -1表示没有任何方法可以凑出面额i，这时计算就要跳过
            for (int c : stamps) {
                if (c <= amount - i) { // 细节2：当心数组越界
                    int s = i + c; // 当前新的面额
                    int cnt = dp[i] + 1; // 组成面额s所需的邮票数
                    if (dp[s] == -1 || dp[s] > cnt) 
                        dp[s] = cnt;
                }
            }
        }
    }
    return dp[amount];
}

int main() {
    vector<int> stamps = {1, 6, 10};
    int amount = 13;
    int a = minStamps(stamps, amount);
    cout << "最小邮票张数: " << a << endl;
    return 0;
}